学界 | 超大规模图计算在阿里巴巴的应用都有哪些？四篇KDD oral论文抢先看（附论文下载）| KDD 2018

AI 科技评论按：本文为阿里巴巴提供的 KDD 2018 解读稿件。这一事件在雷锋网学术频道 AI 科技评论旗下数据库项目「AI 影响因子」中有相应加分。

过去 30 年，随着高质量实验技术和互联网高速连接的出现，越来越大量的数据已经可以自动化的生产和传输。随之而来是，工业界、学术界、甚至个人都必须面对大型数据处理的挑战，如何从这些大量高维异构的数据中挖掘有价值的信息，一直是数据挖掘从业人员们在解决的问题。「数据挖掘」，通常也为「数据库中的知识发现」（https://core.ac.uk/download/pdf/81721154.pdf），是一个充分利用各种统计、机器学习、人工智能模型和与之相适应的计算平台，去试图自动解释大型数据集的一个跨领域交叉学科。KDD (ACM SIGKDD CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING) 正是这个领域的顶级会议。从实际数据和与之相关的业务以及 KDD 被接收的文章，我们可以总结出数据挖掘的几个比较重要的发展趋势：

• 多模态数据挖掘：随着技术可以更加有效地从多种渠道收集数据，比如音频、视频、文字、图像等，这也是现在越来越被重视的一个方向，而数据本身也更更加有效的以各种方式进行存储。如何进行跨领域的有效建模，比如多任务学习 (multi-task learning)，迁移学习 (transfer learning)，强化学习（reinforcement learning）等，都是重点的发展模型。

• 全域数据挖掘：该方法涉及从移动设备和 IoT 设备等挖掘数据以获得关于个人的信息。尽管在这种类型中存在诸如复杂性、隐私性、成本等的若干挑战，但是该方法在各种行业中具有很大的机会，特别是在研究人机交互方面。

• 分布式数据挖掘：这种类型的数据挖掘越来越受欢迎，因为它涉及挖掘存储在不同公司位置或不同组织的大量信息，并且任何的算法也已经很难在单机版对全网数据进行训练和推理。此外适应度更高的算法也可以用于从不同位置提取数据，并根据它们提供适当的见解和报告。

• 时空数据挖掘：这是一种新的趋势类型的数据挖掘，其包括从有周期性和季节性趋势的环境，天文和地理数据中提取信息，其中还包括从外太空获取的图像。这种类型的数据挖掘可以揭示诸如距离和拓扑的各个方面，其主要用于动态的地理信息系统和其他导航应用，这种做法也有助于分析在正常系列事件之外发生的随机事件。与我们密切相关的问题也是越来越普及，比如新零售，如何有效结合动态的线上线下数据对访问顾客的购买模式和行为进行建模，就是一个非常有挑战的时空数据模型问题。

• 图计算模型在大数据公司，尤其是 IT 公司是非常流行的一大类模型，因为是很多实际问题的最直接的解决方法。图计算大致可以分为同构图（homogeneous graph）和异构图（heterogeneous graph），后者是在节点或者边的种类大于等于 2 的情况下。此外知识图谱也是异构图中的一种重要应用，即一种基于语义学的图模型（a semantic graphical model）。除了了传统的图计算模型，如大家熟知的 LPA、 Random Walk 及各种变形、CC 等，随着深度学习的大量成功落地，Graph Embedding 也变得越来越流行。简单说来，Graph Embedding 也是通过深度学习模型对节点或者边进行 feature engineering。近几年，随着数据的多样化，数据量的大幅度提升和算力的突破性进展，图计算的发展和应用有井喷之势，各大公司也相应推出图计算平台，例如 Google Pregel， Facebook Giraph，腾讯星图，华为 GES 等。

其中超大规模图数据挖掘也可以认为是前面几个趋势的一个汇总，也将是未来 3~5 年年数据挖掘的一个大的集中爆发点。比如 DeepMind、谷歌大脑、MIT 等 27 位作者最近推出重磅论文（https://arxiv.org/pdf/1806.01261.pdf），表示单纯的深度学习已经成熟，而基于图计算的深度学习将端到端学习与归纳推理相结合，有望解决深度学习无法进行关系推理的问题。超大规模图计算在大数据公司发挥着越来越重要的作用，尤其是以深度学习和图计算结合的大规模图表征为代表的系列算法。

超大规模图计算在大数据公司发挥着越来越重要的作用，尤其是以深度学习和图计算结合的大规模图表征为代表的系列算法在阿里的诸多业务场景都取得了阶段性成果。阿里巴巴生态体系的数据是极其丰富多样的，涵盖着从购物、出行到娱乐、支付等各个方面信息。比如个性化推荐系统作为一种信息过滤的重要手段，可以依据我们的习惯和爱好推荐合适的商品或者服务，但是传统的推荐系统容易出现稀疏性、冷启动和信息重复性的问题，而知识图谱作为大规模图表征的一类重要模型正在成为一种新兴类型的推荐辅助信息，可以将自然人的全域信息有效的结合起来，真正挖掘、理解每个人的需求，在每个业务域推出消费者真正感兴趣的潜在商品。我们正在致力于研发新一代推荐系统，可以高效的对于超过几十亿节点，千亿的边进行推理分析。基于这个挑战，我们正竭力力寻找能够在信息检索、分布式计算、大规模系统设计、机器学习、人工智能、自然语言处理等相关领域带来新鲜理念的工程师和科学家。对于这个课题感兴趣的同学欢迎和笔者进行更深入讨论 ([e-mail])。

下面我们就会具体介绍一下我们最近取得的一些成果和 KDD 接收文章，包括： 

fraud detection（SPARC: Self-Paced Network Representation for Few-Shot Rare Category Characterization）；recommendation（Interactive Paths Embedding for Semantic Proximity Search on Heterogeneous Graphs）；entity resolution (Mobile Access Record Resolution on Large-Scale Identifier-Linkage Graphs) with deep model interpretations (Adversarial Detection with Model Interpretation)。

1. 天才的 SPARC: 阿里巴巴在罕见的分类分析的进展

在网络平台上，稀有数据通常是最有价值的。罕见的类别分析对于防止计算机网络入侵，发现社交媒体上的热门话题以及检测欺诈性在线交易至关重要。但是，找到这些数据可能会很困难。就像大海捞针中的谚语一样，它们通常隐藏在正常数据点之间并且与正常数据点不可分割，并且标记罕见的类别示例非常昂贵。为了有效地分析数据集中的罕见类别，算法必须是快速学习者。阿里巴巴的技术团队与亚利桑那州立大学和腾讯医学人工智能实验室合作，创建了 SPARC，这是一个自定进度的框架，以互利的方式逐步学习罕见的面向类别的网络表示和表征模型。

• 按照自己的节奏学习

SPARC 的灵感来自课程学习。课程学习范式模仿人类的认知过程：基础模型从任务的简单方面训练到基于预定课程的更难的方面。

虽然这个概念已经应用于许多不同的情况，但试错设计很难在现实世界中应用。然而，一种新的学习范式通过使用自定进度的调节器最小化损失函数来自动学习课程。这被称为自定进度学习。研究小组建立在这种自定进度学习的理念之上，将其应用于稀有类别分析的场景，缺少标记的例子，以便逐步并同时学习稀有类别嵌入表示和表征模型。SPARC 同时学习图形嵌入并以互利的方式预测稀有类别示例。该框架能够在给定网络（例如不同网络大小）中对不平衡类成员资格进行建模。SPARC 能够从少量标记的稀有类别示例中学习，从而最大限度地降低标签成本。此外，使用 SPARC 的面向类别的表示能够在嵌入空间中广泛地分离多数类和少数类，这些类在网络拓扑和特征方面是不可分割的。

SPARC 自己节奏的模型示意图

• 将 SPARC 置于行动中

为了测试 SPARC 在该领域的有效性，研究人员收集了来自书目协作网络，NLP 网络和社交网络的数据集。该算法按照以下标准与两个无监督网络嵌入算法 DeepWalk 和 LINE 以及另一个半监督框架 PLANETOID 进行了比较：分类准确性，发现的稀有类别示例的百分比和正在检索的真实罕见示例的比率。

在大多数情况下，SPARC 在所有数据集和评估指标上的表现优于竞争最先进的方法。虽然半监督嵌入网络在分离类别时表现优于无监督方法，但 SPARC 在聚类罕见示例方面表现优异，并且能够仅使用一个标记为罕见类别的示例进行训练。此外，SPARC 更强大，误差小于比较方法。

全文地址：http://t.cn/RkCI3cq

由 SPARC 和三个竞争框架提取的网络布局可视化

2. 谁知道谁：用交互式路径嵌入正确的人

Web 平台最吸引人的功能之一是用户与他人联系的能力。例如，在社交媒体上，用户甚至可能不必在平台推荐新连接之前主动搜索朋友。在这些网络平台的表面下面是用户之间庞大的连接网络，并且该网络的大部分依赖于「语义邻近搜索」：将网络中的对象作为查询并根据语义关系对其他对象进行排名。语义邻近搜索查看诸如位置，就业地点和学校等特征，以确定通过这些连接隐含的语义关系。从那里，搜索将用户作为查询并询问哪些其他用户可能是邻居，同事或同学，相应地对他们进行排名。然后，这些排名用于支持诸如社交媒体上的推荐连接，参考书目网络上的顾问/建议者连接以及在电子商务平台上链接用户身份等功能。

在具有大型用户基础的网站（例如 Facebook）上，如上所述的异构图形可能会很快变得复杂

然而，语义邻近搜索并不完美。异构列表上的语义关系并不总是明确的，并且对象之间可能缺少链接。先前对语义接近度的研究已经尝试测量与连接查询对象和目标对象的路径的语义接近度。但是，这些路径在建模中是弱耦合的，每个路径都是单独处理的。它们的输出仅在最后阶段汇总，限制了模型形成对象之间相互依赖关系的完整画面的能力。阿里巴巴的技术团队与来自浙江大学和新加坡高级数字科学中心的研究人员合作，开发了交互式路径嵌入（IPE），以更强地耦合语义邻近搜索路径，找到用户之间的联系，这些联系可能会被当前基线忽视。

• IPE 模型的建立

阿里巴巴的研究团队介绍了交互路径的概念，同时处理多条路径并在它们之间添加依赖关系。结果，这些路径被认为是强耦合的。然后将这些交互式路径嵌入到低维向量中，该向量可以捕获用户之间的语义关系的全部范围。

IPE 框架的模型

从那里开始，研究人员利用了一种无循环的改组机制。不希望图形结构中的循环，因为它们使得两个节点更难以彼此到达。这种机制改变了路径的顺序，以消除不同的循环并最大化路径效率。然后，门控循环单元（GRU）架构嵌入交互路径，并允许每个 GRU 模拟来自其他 GRU 的相互依赖性。最后，交互路径结构嵌入输出被聚合为单个向量，然后可以用于估计语义关系接近度。

• IPE 在实际中的使用

为了测试 IPE 在该领域的有效性，阿里巴巴的技术团队寻找不同类型的异构网络，如 LinkedIn，Facebook，DBLP 和淘宝。在实验中，IPE 和其他几个语义用户搜索基线的任务是根据每个网络特有的特征集定义不同类型的关系。研究人员为每个测试查询用户和每个所需的语义关系构建了理想的排名。他们将这种理想排名与各种最先进的语义用户搜索算法生成的排名进行了比较。在所有这些测试中，IPE 不仅在竞争基线方面表现优异，而且在自身的降级版本方面也表现优异，通常显着。这验证了交互路径结构，并为扩展 IPE 以处理异构网络中的属性和动态以进行语义邻近搜索打开了大门。

全文地址：http://t.cn/RkCIsR0

3. 通过你的手机可以对你做人物画像吗？

电子商务时代正在见证移动互联网用户的快速增长。主要的电子商务公司现在每天都会看到数十亿的移动访问实例，并且隐藏在这些记录中的是有价值的用户行为特征，例如购物偏好和浏览模式。但是，为了从庞大的数据集中提取此信息，需要将记录链接到相应的移动设备，这一过程称为移动访问记录解析（MARR）。MARR 面临两大挑战：

1. 访问记录中的设备标识符和其他属性可能缺失或不可靠。

2. 数据集包含数百万台设备的数十亿访问记录。

目前，还没有开发出现有方法来解决如此大规模使用移动设备标识符的问题。

• 我们可能不知道你在用什么设备

根据国际电信联盟（ITU）的一份新报告，2017 年全球移动互联网用户（非用户）数量达到 77.4 亿。随着移动电话取代台式电脑成为最广泛使用的数字平台，移动用户偏好的特征他们的访问记录中的行为模式变得非常重要。与传统的博客相比，移动访问记录主要依赖于 cookie 来跟踪用户行为，因此可以更清晰地了解访问记录中具有各种 ID 的互联网用户。这些 ID 包括：

1. 国际移动设备身份（IMEI）- 用于识别设备的唯一标识符。

2. 国际移动用户识别码（IMSI）- 用于识别存储在 SIM 卡中的蜂窝网络中的用户。

3. UserTrack 设备 IDentity（UTDID）。

IMEI 和 IMSI 分别是一个智能手机和手机号码的标识符。另一方面，UTDID 与这两个基于硬件的标识符完全不同，因为它由阿里巴巴（中国的跨国电子商务公司）生成和使用，用于设备识别。利用这些 ID，可以将访问记录映射到相应的移动电话或应用程序，从而生成更高质量的用户配置文件。将访问记录映射到移动电话或应用程序似乎是一件简单的事情，因为可以使用诸如 IMEI，IMSI 和 UTDID 之类的 ID 来唯一地识别设备和应用程序。但是，从实际应用中收集的数据远非完美。将丢失属性值，噪声（有问题和误导性）ID 和 ID 转换问题。ID Shift 转换的一种方式是当设备在安装新 SIM 卡时获得新的 IMSI。

我们的移动访问记录中有大量数据

• 让我们的设备自己发声

阿里巴巴技术团队观察到，访问记录中的一个或两个 ID 的 ID 转换可能会不时发生，但很少发生在所有三个 ID 中。受此观察的启发，他们使用三个 ID（IMEI，IMSI，UTDID）的组合（他们称之为「IDSET」）来可靠地识别来自特定移动设备的访问记录。上面给出了 IDSET 的示例记录由 IDSET 标识，即 IMEI，IMSI 和 UTDID 的组合。基于 IDSET 的概念，他们引入了移动访问记录解决（MARR）问题。MARR 问题的目的是识别每个访问记录的物理设备，因为每个访问记录由一个特定的移动设备生成。该团队的目标是根据设备对访问记录进行分组，该设备可用于为设备用户生成配置文件。考虑到数据集的庞大规模和较差的数据质量主要是由于 ID 转移问题，MARR 是一个非常具有挑战性的问题。因此，该团队还提出了一个稀疏标识符链接图（SPI-Graph），并附带丰富的移动设备分析数据，以准确地将移动访问记录与设备进行匹配（当数据集中的某些预期值丢失时，数据被视为「稀疏」，这是一般大规模数据分析中的常见现象）。到目前为止，大规模实际数据集的广泛实验结果验证了团队算法的有效性和效率。这些结果还意味着团队现在希望调查他们如何进一步将特定设备的移动访问记录分组到访问会话中，从而更好地表征用户配置文件。

全文地址：http://t.cn/RkCMqGf

4. 了解你的对手：阿里巴巴如何培养更智能的在线欺诈探测器

随着越来越多的实际应用程序，机器学习（ML）系统最近成为一种有前途的在线欺诈检测工具。然而，在大多数 ML 任务处理固定数据集的情况下，欺诈检测对能够在暴露时能够适应的智能人类行为者起作用，这意味着 ML 模型在移位数据集中易于变得静止。以前建立更能抵抗变化对手的探测器的努力依赖于诸如分类和特征识别增强，死记硬背对抗训练和深度神经网络应用之类的方法。每一个都有其自身的局限性，但一个主要的反复出现的问题是「黑匣子」难题。研究人员通常无法获取有关这些方法的内部运作的详细信息，否认他们可以帮助他们进一步发展这些方法的重要见解。现在，阿里巴巴的研究人员已经开发了一种对抗训练方法，该方法基于对 ML 模型运作的研究，运用其机制的知识来产生更强大的对手，供他们训练。除了提高探测器的批发稳健性之外，从最少的计算资源中产生具有挑战性的新对手的努力有助于揭示真正的欺诈犯罪者在被发现后可能从给定位置适应的方式。建立在垃圾邮件发送者基本上是人类代理人的前提下，他们在适应时花费的资源有限，该方法展示了如何根据先前攻击的定位来预测未来攻击的「方向」。

• 检查黑箱

ML 欺诈检测系统依靠分类器来过滤内容，将一些垃圾邮件发送者实例视为高可信度，将其他实例视为低可信度实例，具体取决于它们被正确标记的概率。当大量垃圾邮件发送者实体落入其低信任区域时，分类器变得容易受到攻击，因为即使对垃圾邮件发送者这样的易于逃避（EP）样本的微小变化也可能导致其错误分类为合法内容。出于研究目的，阿里巴巴团队将这些 EP 样品作为「种子」处理，用于生成强大的对抗样品，用于探测器培训。然后，他们试图确定种子最容易受到影响的方向，以逃避分类机制，从而以最小的努力绕过检测。利用这些发现，他们生成的对手非常模仿真实的恶意行为，减少了有效训练更强检测机制所需的攻击者总数。通过使用 ML 机制的知识来分析其对沿其边界引入的每个对手的响应，该团队派生出特定于每个实例的本地解释器功能。通过这些信息，他们更新了整体机制，以更好地考虑试验期间引入的个别垃圾邮件威胁的演变。

新系统识别易于逃避的样本，分析潜在的逃避策略，并相应地更新检测模型

基于对 Yelp Review 和 Twitter 帖子数据的实验，仔细的对手选择证明在产生更具挑战性的攻击模拟方面是有效的，在试验期间提供了关于分类器中的弱点的大量信息。然后，这些研究结果被用于为各种攻击制定有效的防御策略，这些策略可用于加强未来检测框架的有效性。展望未来，阿里巴巴正在寻求扩展其垃圾邮件检测工作，以处理实例之间关系链接的高维原始数据和数据集。

全文地址：http://t.cn/RkCMIUZ

访问 https://club.leiphone.com/page/resourceDetail/409 即可移步至AI研习社社区打包下载四篇论文。